The present invention relates to a 1-bit error correction circuit based on cyclic redundancy check (CRC) calculation, and more particularly, to such a 1-bit error correction circuit which is applicable to apparatus which perform digital multiplexing communications. For example, a 1-bit error correction circuit appends a cyclic code as monitoring control data each time multi-frame data is sent and received between apparatus, and is used when the detection and correction of coding errors is performed.
The actual circuit of a 1-bit error correction circuit becomes larger as the number of data bits handled grows and this is in conflict with recent needs for more compact apparatus. It is therefore required to have a 1-bit error correction circuit which has a small circuit size.
FIG. 1 is a view showing the block constitution of a 1-bit error correction circuit using conventional CRC calculations.
The 1-bit error correction circuit uses the cancellation type remainder generation method. In FIG. 1 inside the dotted line 11 is an 8-bit parallel development cancellation type remainder generation portion.
As shown in FIG. 2A, the input data to this 1-bit error correction circuit is the cyclic code H comprising the 32-bit information portion H1.about.H4 and the 8-bit check portion H5, and here, the 40 bits of H1.about.H5 are handled as single frame.
When the cyclic signal H which is the input data is input to the 1-bit error correction circuit shown in FIG. 1, input data H1.about.H5 are successively and respectively input in 8-bit parallel H1.about.H5 to the 1-bit error correction circuit. FIG. 2A shows the cyclic signal which is the input data. The cyclic signal H is comprised from the information portion H1.about.H4, and the check portion H5, and one frame has a total of 40 bits.
FIG. 2B shows 1 byte (H4) of the cyclic signal, and is the contents of the code H4 of the information portion of the cyclic signal H. FIG. 2B shows the case for when the 7th of the 8 bits is an error.
The cancellation type remainder generation portion 11 (syndrome generation portion) for 8-bits parallel development is comprised of the exclusive OR circuits (EOR) 12,21, a shift register (SR) 13, a first remainder calculation circuit 14, shift register 15.about.19, and a second remainder calculation circuit (EOR) 20.
The exclusive OR circuit 12 calculates of the exclusive OR of the 8-bit input parallel data and input parallel data other than the 8-bit data, and outputs the result as 8-bit parallel data. In FIG. 1, the exclusive OR circuit 12 performs exclusive OR of the cyclic signal H which is successively input as the input data to H1.about.H5, and the 8-bit output data of the first remainder calculation circuit 14, and outputs the result to the shift register (SR) 13.
The shift register (SR) 13 is comprised so as to be connected in parallel to eight 1-bit flip flops, stores the input 8-bit data, and outputs the stored 8-bit data.
On the basis of the function f(x), the first remainder calculation circuit 14 performs a remainder calculation on the 8-bit data which is input from the shift register (SR) 13 and the shift register 15.
In FIG. 3, at time t.sub.0, the first remainder calculation circuit 14 outputs the remainder f(C) as the initial value C which is the random value output from the shift register (SR) 13. This initial value C is also output to the first remainder calculation circuit 14 and the shift register 15.
At this time, the exclusive OR circuit 12 calculates of the exclusive OR of the remainder f(C) and the H1 which is supplied as the input data, and outputs to the input side of the shift register (SR) 13.
At time t.sub.1 when the clock signal from the timing generation circuit (not shown in the figure), is input to the 1-bit error correction circuit, H1 Ex f(C) is output to the shift register (SR) 13. In FIG. 3, H1 .largecircle. f(C) is the exclusive OR of the input data H1 and the remainder f(C). The .largecircle. of "H1s.largecircle.f(c)" is expressed as "Ex" in this specification.
The shift register (SR) 13 stores and outputs the exclusive OR H1 Ex f(C) to the first remainder calculation circuit 14 and the shift register 15. The shift register 15 stores C at time t.sub.1.
In addition, the first remainder calculation circuit 14 uses the function f(x) and the input exclusive OR of "H1Ex f(C)" to output "(H1Ex f(C))=f(H1) Ex f.sup.2 (C)" to the exclusive OR circuit 12. The exclusive OR circuit 12 uses the "f(H1)Ex f.sup.2 (C)" which has been input from the first remainder calculation circuit 14, as input data to perform exclusive OR calculation on H2 which is supplied after H1, and outputs that result to the shift register (SR) 13.
At time t.sub.2 when the next clock signal is supplied, the shift register (SR) 13 outputs "H2 Ex f(H1)Ex f.sup.2 (C)" to the first remainder calculation circuit 14 and the shift register 15.
At time t.sub.2, the shift register 15 stores the "H1 Ex f(C)" which is the output of the shift register (SR) 13 at the time t.sub.1, takes the initial value C stored in the shift register 15 at time t.sub.0 and shifts it to the shift register 16.
In addition, the first remainder calculation circuit 14 to which is input "H2 Ex f(H1)Ex f.sup.3 (C)", outputs "f(H2)Ex f.sup.2 (H1)Ex f.sup.2 (C)" to the exclusive OR circuit 12. The exclusive OR circuit 12 calculates the exclusive OR of the "f(H2)Ex f.sup.2 (H1)Ex f.sup.3 (C)" and H3, and outputs that result to the shift register (SR) 13.
At time t.sub.3, when there is the input of the clock signal from the timing generation circuit (not shown in the figure) to the 1-bit error correction circuit, the shift register (SR) 13 stores "2Ex f(H2)Ex f.sup.2 (H1)Ex f.sup.3 (C)" and outputs it to the first remainder calculation circuit 14 and the shift register 15.
At this time, the shift register 15 has stored in it the "H2Ex f(H1)Ex f.sup.2 (C)" which has been output from the shift register (SR) 13 at the time t.sub.2, and the "H1 Ex f(C)" which has been stored in the shift register 15 at the time t.sub.2 is shifted and stored, and intial value C is stored in the shift register 17.
In addition, at time t.sub.3, the first remainder calculation circuit 14 to which "H3 Ex f(H2)Ex f.sup.2 (H1)Ex f.sup.3 (C)" has been input, outputs "f(H3)Ex f.sup.2 (H2)Ex f.sup.2 (H1) Exf.sup.4 (C)" to the exclusive OR circuit 12. The exclusive OR circuit 12 calculates the exclusive OR of "H4" and the "f(H3)Ex f.sup.2 (H2)Ex f.sup.3 (H1)Ex f.sup.4 (C)", and outputs that result to the shift register (SR) 13.
At time t.sub.4 when there is the supply to the 1-bit error correction circuit of the clock signal from the timing generation circuit, the shift register (SR) 13 stores "H4Ex f(H3)Ex f.sup.2 (H2)Ex f.sup.3 (H1)Ex f.sup.4 (C)" and outputs that to the first remainder calculation circuit 14 and the shift register 15.
At time t.sub.3, the shift register 15 stores the "H3Ex f(H2)Ex f.sup.2 (H1)Ex f.sup.3 (C)" which has been output from the shift register (SR) 13.
The shift register 17 stores the shifted "H1 Ex f(C)" at time t.sub.2 which is stored in the shift register 16, and at time t.sub.4, the shift register 18 stores the C which is stored in the shift register 17.
In addition, at time t.sub.4, the first remainder calculation circuit 14 to which "H4Ex f(H3) Ex f.sup.2 (H2)Ex f.sup.3 (H1)Ex f.sup.4 (C)" was input, output "f(H4) Ex f.sup.2 (H3) f.sup.3 (H2) Ex f.sup.4 (H1)Ex f.sup.5 (C)" to the exclusive OR circuit 12. The exclusive OR circuit 12 performs a calculation of the exclusive OR of "H5" and the "f(H4)Ex f.sup.2 (H3)Ex f.sup.3 (H2)Ex f.sup.4 (H1)Ex f.sup.5 (C)" and inputs the result to the shift register (SR) 13.
At time t.sub.5 when there is the input of the clock signal from the timing generation circuit to the 1-bit error correction circuit, the shift register (SR) 13 stores the "H5 Ex f(H4)Ex f.sup.2 (H3)Ex f.sup.3 (H2)Ex f.sup.4 (H1)Ex f.sup.5 (C)" and outputs it to the first remainder calculation circuit 14 and the shift register 15.
At time t.sub.5, the shift register 15 stores "H4Ex f(H3)Ex f.sup.2 (H2)Ex f.sup.3 (H1)Ex f.sup.4 (C)" which is output from shift register 13 at time t.sub.4.
The shift register 16 stored the "H4Ex f(H3)Ex f.sup.2 (H2)Ex f.sup.3 (H1)Ex f.sup.4 (C)" output from the shift register (SR) 13. The shift register 17 stores the "H2 Ex f.sup.1 (H1) Ex f.sup.2 (C)" which was stored in the shift register 16 at time t.sub.4. The shift register 18 stores the "H1Ex f(C)" which was stored in the shift register 17 at time t.sub.4. The shift register 19 stores the C which was stored in the shift register 18 at time t.sub.4.
This is to say that at time t.sub.5, "H1Ex f(C)" is input to the shift register 19 and C is output to the second remainder calculation circuit 20.
On the basis of the function f.sup.5 (x), the second remainder calculation circuit 20 performs remainder calculation of the 8-bit data which is input from the shift register 19, and at time t.sub.5 when there is the input of C from the shift register 19, outputs f.sup.5 (C) to the exclusive OR circuit 21.
At time t.sub.5, the "H5Ex f(H4)Ex f.sup.2 (H3)Ex f.sup.3 (H2)Ex f.sup.4 (H1)Ex f.sup.5 (C)" which was output from the shift register (SR) 13 is supplied to the other input terminal of the exclusive OR circuit 21 and so the exclusive OR circuit 21 performs a calculation of the exclusive 5 of "f.sup.5 (C)" and "H5Ex f(H4)5 f.sup.2 (H3)Ex f.sup.3 (H2)Ex f.sup.4 (H1)Ex f.sup.5 (C)". That result "f.sup.5 (C)" is canceled, and "H5Ex f(H4)Ex f.sup.2 (H3)Ex f.sup.3 (H2)Ex f.sup.4 (H1)" is output as the syndrome S for all of H1.about.H5. More specifically, the second remainder calculation circuit 20 outputs a remainder which includes a random value to the exclusive OR circuit 21 but by canceling the random value, the exclusive OR circuit 21 outputs the syndrome S for all of H1.about.H5 which is the actual data.
This syndrome S is expressed as shown by equation (1 in FIG. 4 when the function f(x) used in the remainder calculation is expressed in terms of the matrix .alpha.(x).
Here, for example, when the 8th bit (bit 7) within the bit 0.about.bit 7 of H1 has a 1-bit error, expressing the syndrome S in the format of equation 1 gives equation 2 shown in FIG. 4.
At this time, the matrix equation of .alpha., .alpha..sup.2, .alpha..sup.3, .alpha..sup.4 of equation 2 has a pattern where all of the columns are different and so if the syndrome S expressed by the 40-bit decoder equation 2 corresponding to this pattern is used, then for all of the bits of H1.about.H5, it is possible to identify where the 1-bit error occurred.
However, one decoder uses an OR gate of the 8-bit type and is of a type where an inverter is added to the input side of those 8 bits, in accordance with the error pattern. When a 1-bit error has occurred in the 8'th bit of the column H1, this is detected by the decoder having the inverter added to the input terminal of the 8'th bit of the OR gate.
The decoder 22 shown in FIG. 1 is comprised of this logic. This is to say that the decoder 22 is comprised of eight-input (8-gates) type OR gates attached to inverters in accordance with the all of the error patterns of H1.about.H5, and the eight output lines of the exclusive OR circuit 21 are connected to the input terminals of each of the OR gates. In addition, there are forty output lines for the decoder 22 as shown in FIG. 5.
In FIG. 1, the error correction portion 23 is comprised of AND circuits 24.about.28, shift registers 29.about.33, and the exclusive OR circuit 34.about.38.
Each of the AND circuits 24.about.28 has eight 2-input AND gates. Each of the AND circuits 24.about.28 has a respective output line of the decoder 22 connected to one of the input terminals of the eight AND gates, and the supply line of the pulse signal P1 from the pulse generation circuit (not shown in the figure) is connected to the other input terminal of the AND gates.
The forty output lines of the decoder 22 are grouped into eights corresponding to H1.about.H5, and of these, the eight output lines relating to H1 are connected to the input side of the AND circuit 28, the eight output lines relating to H2 are connected to the input side of the AND circuit 27, the eight output lines relating to H3 are connected to the input side of the AND circuit 26, the eight output lines relating to H4 are connected to the input side of the AND circuit 25 and the eight output lines relating to H5 are connected to the input side of the AND circuit 24.
In addition, the pulse (H level) P1 supplied to each of the AND circuits 24.about.28 are all in synchronism, and is supplied synchronized to the timing t.sub.1 .about.t.sub.5 described above, at intervals of t.sub.5 (t.sub.0, t.sub.5, t.sub.10, t.sub.15, . . .). However, the pulse P1 is not supplied at the same times, but at a timing which has a half-bit delay from the clock signals.
The shift registers 29.about.33 of the error correction portion 23 which has this configuration, store the cyclic signals H1.about.H5 which are input over the time t.sub.1 .about.t.sub.5 of the series described above, and the shift register 33 stores H1, the shift register 32 stores H2, the shift register 31 stores H3, the shift register 30 stores H4 and the shift register 29 stores H5.
Accordingly, at time t.sub.5 when the pulse P1 is supplied to the AND circuit 28, the AND circuit 28 outputs the syndrome of H1 which is included in the syndrome S, to the exclusive OR circuit 38. The exclusive OR circuit 38 performs a calculation of the exclusive OR of the syndrome of H1 and the H1 output from the shift register 33 and outputs the result of the calculation to the correction circuit (not shown in the figure). At this time, any 1-bit errors in the 7th bit of H1 are corrected by this error correction circuit and are output as corrected data H1.
In addition, the AND circuit 27 outputs the syndrome of H2 to the exclusive OR circuit 37. The exclusive OR circuit 37 calculates of the exclusive OR of the syndrome of H2, and the H2 output from the shift register 32, and outputs the result to the shift register 33.
In addition, the AND circuit 26 outputs the syndrome of H3 to the exclusive OR circuit 36. The exclusive OR circuit 36 calculates of the exclusive OR of the syndrome of H3, and the H3 output from the shift register 31, and outputs the result to the shift register 32.
In addition, the AND circuit 25 outputs the syndrome of H4 to the exclusive OR circuit 35. The exclusive OR circuit 35 performs a calculation of the exclusive OR of the syndrome of H4, and the H4 output from the shift register 30, and outputs the result to the shift register 31.
In addition, the AND circuit 24 outputs the syndrome of H5 to the exclusive OR circuit 34. The exclusive OR circuit 34 calculates for the exclusive OR of the syndrome of H5, and the H5 output from the shift register 29, and outputs the result to the shift register 30.
Each of the data H2.about.H5 for which such an exclusive OR calculation has been performed is corrected at that time, when there is an error such as that described above for H1.
After this, the corrected data H2' is output at the time t.sub.6. The corrected data H3' is output at the time t.sub.7. The corrected data H4' is output at the time t.sub.8. The corrected data H5' is output at time t.sub.9.
However, the 1-bit error correction circuit shown in FIG. 1 requires an error correction portion 23 which is comprised of the exclusive OR circuit 34.about.38 and AND circuit 24.about.28 which use eight 2-input AND gates and a decoder comprised of forty 8-input OR gates. Accordingly, the scale of the entire circuit of a conventional 1-bit error correction circuit becomes large and there is also the problem that the cost becomes high.